# 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
# 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

# 解法一：暴力遍历 O(n**2)
def IsBalanced_Solution(self, pRoot):
    if pRoot is None:
        return True
    count = (abs(get_level(pRoot.left)-get_level(pRoot.right))<=1) and IsBalanced_Solution(pRoot.left) and IsBalanced_Solution(pRoot.right)
    return count

# 获取一个二叉树的深度
def get_level(root):
    if root is None:
        return 0
    count = max(get_level(root.left),get_level(root.right))+1
    return count

# 解法2：从下往上遍历
class Solution:
    res = True
    def IsBalanced_Solution(self, pRoot):
        # write code here
        self.helper(pRoot)
        return self.res
    def helper(self, root):
        if not root:
            return 0
        if not self.res: return 1
        left = 1 + self.helper(root.left)
        right = 1 + self.helper(root.right)
        if abs(left - right) > 1:
            self.res = False
        return max(left, right)